package com.example.dynamicplanning;

/**
 * @author Administrator
 * 最长公共子串
 */
public class LongestCommonSubstring {
    /**
     * longest common substring
     *
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public static void main(String[] args) {
        LongestCommonSubstring longestCommonSubstring = new LongestCommonSubstring();
        System.out.println(longestCommonSubstring.LCS("3125763", "312763"));
        System.out.println(longestCommonSubstring.DPLCS("31563", "31573"));

    }

    public String LCS(String str1, String str2) {
        // write code here
        String res = "";
        int start = 0;
        int end = 1;
        String temp;
        while (end <= str2.length()) {
            temp = str2.substring(start, end);
            if (str1.contains(temp)) {
                res = temp;
            } else {
                start++;
            }
            end++;
        }
        return res;
    }

    public String DPLCS(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[] dp = new int[len2 + 1];
        int maxLenSub = 0;
        int end = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = len2; j >= 1; j--) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[j] = dp[j - 1] + 1;
                    int t = maxLenSub;
                    maxLenSub = Math.max(maxLenSub, dp[j]);
                    if (maxLenSub > t) {
                        end = i;
                    }
                } else {
                    dp[j] = 0;
                }
            }
        }
        return str1.substring(end - maxLenSub, end);
    }
}

